/*
 * @lc app=leetcode.cn id=707 lang=cpp
 *
 * [707] 设计链表
 */

// @lc code=start
class MyLinkedList {
public:
    MyLinkedList() {

    }
    
    int get(int index) {
        node* pointer = head_;
        int currentIndex = 0;
        while (pointer){
            if (currentIndex == index){return pointer->val_;}
            pointer = pointer->next_;
            currentIndex++;
        }
        return -1;
    }
    
    void addAtHead(int val) {
        node* newHeadNodePtr = new node(val);
        newHeadNodePtr->next_ = head_;
        if (!this->empty()){
            head_->prev_ = newHeadNodePtr;
        }else{
            tail_ = newHeadNodePtr;
        }
        head_ = newHeadNodePtr;
        length_ += 1;
    }

    bool empty(){return length_==0;}
    
    void addAtTail(int val) {
        node* newTailNodePtr = new node(val);
        newTailNodePtr->prev_ = tail_;
        if (!this->empty()){
            tail_->next_ = newTailNodePtr;
        }else{
            head_ = newTailNodePtr;
        }
        tail_ = newTailNodePtr;
        length_ += 1;
    }
    
    void addAtIndex(int index, int val) {
        if (index < 0){return;}
        if (index > length_){return;}

        if (index == length_){
            addAtTail(val);
            return;
        }
        if (index == 0){
            addAtHead(val);
            return;
        }

        node* pointer = head_;
        int currentIndex = 0;
        while (currentIndex != index){
            pointer = pointer->next_;
            currentIndex++;
        }
        // now insert new node in front of pointer
        node* frontNodePtr = pointer->prev_;
        node* newNodePtr = new node(val);
        
        frontNodePtr->next_ = newNodePtr;
        pointer->prev_ = newNodePtr;
        newNodePtr->prev_ = frontNodePtr;
        newNodePtr->next_ = pointer;

        length_ += 1;
    }
    
    void deleteAtIndex(int index) {
        if (index < 0 or index >= length_){return;}

        if (index == 0){
            node* newHeadNodePtr = head_->next_;
            delete head_;
            head_ = newHeadNodePtr;
            if (head_){head_->prev_ = nullptr;}
            length_ -= 1;
            return;
        }
        if (index == length_-1){
            node* newTailNodePtr = tail_->prev_;
            delete tail_;
            tail_ = newTailNodePtr;
            if (tail_){tail_->next_ = nullptr;}
            length_ -= 1;
            return;
        }

        node* pointer = head_;
        int currentIndex = 0;
        while (currentIndex != index){
            pointer = pointer->next_;
            currentIndex++;
        }
        // now delete pointer
        node* frontNodePtr = pointer->prev_;
        node* backNodePtr = pointer->next_;
        delete pointer;
        frontNodePtr->next_ = backNodePtr;
        backNodePtr->prev_ = frontNodePtr;

        length_ -= 1;
    }
private:
    struct node{
        int val_;
        node* prev_ = nullptr;
        node* next_ = nullptr;
        node(int val) : val_(val){}
    };

    node* head_ = nullptr;
    node* tail_ = nullptr;
    int length_ = 0;

    // node headNode_;
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */
// @lc code=end

// ["MyLinkedList","addAtHead","addAtTail","addAtIndex","get","deleteAtIndex","get"]
// [[],[1],[3],[1,2],[1],[1],[1]]

// ["MyLinkedList","addAtHead","addAtIndex","addAtTail","addAtHead","addAtIndex","addAtTail","addAtTail","addAtIndex","deleteAtIndex","deleteAtIndex","addAtTail"]
// [[],[0],[1,4],[8],[5],[4,3],[0],[5],[6,3],[7],[5],[4]]

// [null,null,null,null,null,null,null,null,null,null,null,null]

// ["MyLinkedList","addAtHead","get","addAtTail","deleteAtIndex","get","addAtTail","get","deleteAtIndex","addAtHead","addAtHead","addAtHead","addAtHead","addAtTail","addAtTail","addAtTail","deleteAtIndex","addAtIndex","addAtHead","addAtIndex","addAtTail","addAtHead","get","addAtHead","addAtTail","addAtHead","addAtHead","get","addAtHead","addAtHead","addAtTail","addAtHead","addAtTail","addAtTail","deleteAtIndex","addAtTail","deleteAtIndex","addAtHead","addAtTail","addAtIndex","addAtHead","addAtTail","addAtHead","deleteAtIndex","deleteAtIndex","addAtHead","addAtTail","addAtTail","addAtHead","addAtHead","get","deleteAtIndex","addAtHead","addAtTail","deleteAtIndex","addAtTail","addAtTail","addAtTail","addAtIndex","addAtIndex","get","addAtTail","addAtTail","addAtHead","addAtTail","addAtTail","addAtHead","get","addAtTail","get","deleteAtIndex","addAtHead","addAtHead","addAtHead","addAtIndex","addAtIndex","deleteAtIndex","get","addAtTail","addAtTail","addAtHead","get","addAtHead","addAtTail","addAtIndex","deleteAtIndex","addAtHead","addAtHead","addAtTail","get","deleteAtIndex","addAtHead","addAtTail","addAtTail","addAtHead","addAtHead","deleteAtIndex","get","addAtHead","addAtTail","addAtHead","addAtTail"]\n[[],[24],[1],[18],[1],[1],[30],[2],[1],[3],[3],[33],[97],[43],[12],[10],[1],[1,56],[30],[8,83],[57],[74],[5],[98],[72],[34],[61],[6],[70],[24],[91],[99],[13],[10],[17],[84],[16],[73],[88],[4,19],[59],[41],[57],[10],[18],[2],[12],[25],[1],[77],[1],[7],[34],[87],[13],[4],[12],[11],[10,92],[21,55],[11],[38],[31],[45],[4],[21],[38],[4],[88],[12],[22],[40],[22],[23],[13,96],[24,50],[8],[14],[25],[53],[42],[6],[58],[55],[18,72],[13],[30],[97],[59],[47],[24],[37],[26],[31],[93],[66],[11],[43],[70],[36],[31],[28]]

// [null,null,-1,null,null,-1,null,-1,null,null,null,null,null,null,null,null,null,null,null,null,null,null,3,null,null,null,null,56,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,1,null,null,null,null,null,null,null,null,null,61,null,null,null,null,null,null,1,null,92,null,null,null,null,null,null,null,19,null,null,null,34,null,null,null,null,null,null,null,21,null,null,null,null,null,null,null,12,null,null,null,null]

// ["MyLinkedList","addAtHead","deleteAtIndex"]\n[[],[1],[0]]

int main(){
    MyLinkedList list;
    list.addAtHead(1);
    list.deleteAtIndex(0);

    // list.addAtIndex(1, 4);
    // list.addAtHead(5);
    // list.addAtIndex(4, 3);
    // list.addAtTail(0);
    // list.addAtTail(5);
    // list.addAtIndex(6, 3);
    // list.deleteAtIndex(7);
    // list.deleteAtIndex(5);
    // list.addAtTail(4);
}